# 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
#
#  返回被除数 dividend 除以除数 divisor 得到的商。
#
#  整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
#
#
#
#  示例 1:
#
#  输入: dividend = 10, divisor = 3
# 输出: 3
# 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
#
#  示例 2:
#
#  输入: dividend = 7, divisor = -3
# 输出: -2
# 解释: 7/-3 = truncate(-2.33333..) = -2
#
#
#
#  提示：
#
#
#  被除数和除数均为 32 位有符号整数。
#  除数不为 0。
#  假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
#
#  Related Topics 数学 二分查找
#  👍 398 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int

        """

        # 被除数  = 0 的情况
        if not dividend:
            return 0

        # 除数是 1 的情况
        if abs(divisor) == 1:
            if dividend == 2147483647:
                return 2147483647 if divisor > 0 else -2147483648
            else:
                if dividend == -2147483648:

                    return 2147483647 if divisor < 0 else dividend

        # 存在负数相除的情况
        if dividend < 0 < divisor:
            return -self.divide(-dividend, divisor)

        elif dividend > 0 > divisor:
            return -self.divide(dividend, -divisor)

        elif dividend < 0 and divisor < 0:
            return self.divide(-dividend, -divisor)

        if dividend < divisor:
            return 0

        r = 1
        d = divisor

        while dividend > d * 2:
            r = r * 2
            d = d * 2

        res = r + self.divide(dividend - d, divisor)

        return 2147483647 if res >= 2147483648 else res


# leetcode submit region end(Prohibit modification and deletion)


if __name__ == '__main__':
    print(Solution().divide(2147483648, 1))
